Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 39/115

Q: Which matrix has most of the elements (not all) as Zero?
A. Identity Matrix
B. Unit Matrix
C. Sparse Matrix
D. Zero Matrix
Solution: Sparse Matrix is a matrix in which most of the elements are Zero. Identity Matrix is a matrix in which all principle diagonal elements are 1 and rest of the elements are Zero. Unit Matrix is also called Identity Matrix. Zero Matrix is a matrix in which all the elements are Zero.
Q: What is the relation between Sparsity and Density of a matrix?
A. Sparsity = 1 – Density
B. Sparsity = 1 + Density
C. Sparsity = Density*Total number of elements
D. Sparsity = Density/Total number of elements
Solution: Sparsity of a matrix is equal to 1 minus Density of the matrix. The Sparsity of matrix is defined as the total number of Zero Valued elements divided total number of elements.
Q: Who coined the term Sparse Matrix?
A. Harry Markowitz
B. James Sylvester
C. Chris Messina
D. Arthur Cayley
Solution: Harry Markowitz coined the term Sparse Matrix. James Sylvester coined the term Matrix. Chris Messina coined the term Hashtag and Arthur Cayley developed the algebraic aspects of a matrix.
Q: Is O(n) the Worst case Time Complexity for addition of two Sparse Matrix?
A. True
B. False
C. ....
D. ....
Solution: In Addition, the matrix is traversed linearly, hence it has the time complexity of O(n) where n is the number of non-zero elements in the largest matrix amongst two.
Q: The matrix contains m rows and n columns. The matrix is called Sparse Matrix if ________
A. Total number of Zero elements > (m*n)/2
B. Total number of Zero elements = m + n
C. Total number of Zero elements = m/n
D. Total number of Zero elements = m-n
Solution: For matrix to be Sparse Matrix, it should contain Zero elements more than the non-zero elements. Total elements of the given matrix is m*n. So if Total number of Zero elements > (m*n)/2, then the matrix is called Sparse Matrix.
Q: Which of the following is not the method to represent Sparse Matrix?
A. Dictionary of Keys
B. Linked List
C. Array
D. Heap
Solution: Heap is not used to represent Sparse Matrix while in Dictionary, rows and column numbers are used as Keys and values as Matrix entries, Linked List is used with each node of Four fields (Row, Column, Value, Next Node) (2D array is used to represent the Sparse Matrix with three fields (Row, Column, Value).
Q: Is Sparse Matrix also known as Dense Matrix?
A. True
B. False
C. 
D. 
Solution: Sparse Matrix is a matrix with most of the elements as Zero elements while Dense Matrix is a matrix with most of the elements as Non-Zero element.
Q: Which one of the following is a Special Sparse Matrix?
A. Band Matrix
B. Skew Matrix
C. Null matrix
D. Unit matrix 
Solution: A band matrix is a sparse matrix whose non zero elements are bounded to a diagonal band, comprising the main diagonal and zero or more diagonals on either side.
Q: In what way the Symmetry Sparse Matrix can be stored efficiently?
A. Heap
B. Binary tree
C. Hash table
D. Adjacency List
Solution: Since Symmetry Sparse Matrix arises as the adjacency matrix of the undirected graph. Hence it can be stored efficiently as an adjacency list.
Q: What is the time complexity of the code that uses merge sort for determining the number of inversions in an array?
A. O(n2)
B. O(n)
C. O(log n)
D. O(n log n)
Solution: The code of merge sort is slightly modified in order to calculate the number of inversions in an array. So the time complexity of merge sort remains unaffected and hence the time complexity is O(n log n).

You Have Score    /10